/// @tags: NTT Poly PolyLn
#include <algorithm>
#include <cctype>
#include <cstdio>

typedef long long ll;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 1 << 19, mod = 1004535809, G = 3, invG = 334845270;
int n, Cvt[N << 2], f[N], g[N], fact[N], maxl = 1;

inline ll qpow(ll base, ll exp) {
  ll res = 1;
  while (exp) {
    if (exp & 1) res = res * base % mod;
    base = base * base % mod;
    exp >>= 1;
  }
  return res;
}

inline void NTT(int *const f, bool typ, const int len) {
  int *const cvt = Cvt + len - 1;
  for (int i = 1; i < len; ++i)
    if (i < cvt[i]) std::swap(f[i], f[cvt[i]]);
  for (int i = 2; i <= len; i <<= 1) {
    int mid = i >> 1, wn = qpow(typ ? G : invG, (mod - 1) / i);
    for (int j = 0; j < len; j += i) {
      ll wk = 1;
      for (int k = 0; k < mid; ++k, (wk *= wn) %= mod) {
        int t = wk * f[j + k + mid] % mod;
        if ((f[j + k + mid] = f[j + k] - t) < 0) f[j + k + mid] += mod;
        if ((f[j + k] += t) >= mod) f[j + k] -= mod;
      }
    }
  }
  if (!typ) {
    ll inv = qpow(len, mod - 2);
    for (int i = 0; i < len; ++i) f[i] = inv * f[i] % mod;
  }
}

inline void polyInv(int *const res, int *const f, const int len) {
  static int h[N];
  res[0] = qpow(f[0], mod - 2);
  int l = 1;
  while (l <= len) {
    l <<= 1;
    for (int i = 0; i < l; ++i) h[i] = f[i], h[i + l] = 0;
    NTT(h, true, l << 1), NTT(res, true, l << 1);
    for (int i = 0; i < l << 1; ++i) {
      res[i] = static_cast<ll>(res[i]) *
               ((2ll - static_cast<ll>(res[i]) * h[i] % mod + mod) % mod) % mod;
    }
    NTT(res, false, l << 1);
    for (int i = std::min(len, l); i < l << 1; ++i) res[i] = 0;
  }
}

inline void polyLn(int *const res, int *const f, const int len) {
  static int invf[N];
  polyInv(invf, f, len);
  int *const df = f;
  for (int i = 0; i + 1 < len; ++i) df[i] = static_cast<ll>(f[i + 1]) * (i + 1) % mod;
  df[len - 1] = 0;
  NTT(df, true, len), NTT(invf, true, len);
  for (int i = 0; i < len; ++i) res[i] = static_cast<ll>(df[i]) * invf[i] % mod;
  NTT(res, false, len);
  for (int i = len - 1; i; --i) res[i] = qpow(i, mod - 2) * res[i - 1] % mod;
  res[0] = 0;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4841 [集训队作业2013]城市规划.in", "r", stdin);
  freopen("P4841 [集训队作业2013]城市规划.out", "w", stdout);
#endif
#endif

  ++read(n);
  while (maxl < n) maxl <<= 1;
  for (int bit = 0, len = 1; len <= maxl << 2; ++bit, len <<= 1) {
    int *const cvt = Cvt + len - 1;
    for (int j = 1; j < len; ++j) cvt[j] = cvt[j >> 1] >> 1 | ((j & 1) << (bit - 1));
  }
  fact[0] = 1;
  --n;
  for (int i = 1; i <= n; ++i) fact[i] = static_cast<ll>(fact[i - 1]) * i % mod;
  for (int i = 0; i <= n; ++i) {
    g[i] = qpow(fact[i], mod - 2) * qpow(2, static_cast<ll>(i) * (i - 1) >> 1) % mod;
  }
  polyLn(f, g, maxl);
  printf("%lld", static_cast<ll>(fact[n]) * f[n] % mod);
  return 0;
}